class Solution {
private:
    const int kmod=1000000007;
public:
    int InversePairs(vector<int> data) {
        int ret=0;
        vector<int> tmp(data.size());
        merge_sort(data,tmp,0,data.size()-1,ret);
        return ret;
    }
    void merge_sort(vector<int> &arr,vector<int> &tmp,int l,int r,int &ret){
        if(l>=r)//只有一个元素 返回
            return;
        int mid=l+((r-l)>>1);
        merge_sort(arr,tmp,l,mid,ret);
        merge_sort(arr,tmp,mid+1,r,ret);
        merge(arr,tmp,l,mid,r,ret);
    }
    void merge(vector<int> &arr,vector<int> &tmp,int l,int mid,int r,int &ret){
        int i=l,j=mid+1,k=0;
        while(i<=mid&&j<=r){//归并过程
            if(arr[i]>arr[j]){
                tmp[k++]=arr[j++];
                ret+=(mid-i+1);//左右区间都是有顺序的  如果arr[i]>arr[j]  那么所有左区间的数均大于arr[j]
                ret%=kmod;//防溢出
            }
            else
                tmp[k++]=arr[i++];
        }
        while(i<=mid)
            tmp[k++]=arr[i++];
        while(j<=r)
            tmp[k++]=arr[j++];
        for(k=0,i=l;i<=r;i++,k++)
            arr[i]=tmp[k];
    }
};